//309 Best Time to Buy and Sell Stock with Cooldown
/*
给定一段时间内每天的股票价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股
票，求最大的收益

输入输出样例
	输入一个一维整数数组，表示每天的股票价格；输出一个整数，表示最大的收益

Input: [1,2,3,0,2]
Output: 3
*/
int maxProfit(vector<int> &prices)
{
	int n = prices.size();
	if (n == 0)
	{
		return 0;
	}
	vector<int> buy(n), sell(n), s1(n), s2(n);
	s1[0] = buy[0] = -prices[0];
	sell[0] = s2[0] = 0;
	for (int i = 1; i < n; i++)
	{
		buy[i] = s2[i - 1] - prices[i];
		s1[i] = max(buy[i - 1], s1[i - 1]);
		sell[i] = max(buy[i - 1], s1[i - 1]) + prices[i];
		s2[i] = max(s2[i - 1], sell[i - 1]);
	}
	return max(sell[n - 1], s2[n - 1]);
}

//213
//53
//343
//583
//646
//376
//494
//714